package nowcoder.ali;

import java.util.*;

public class CrossRiver {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) { //for every example
            int pnum = sc.nextInt();
            int[] weights = new int[pnum]; //store weights
            for (int j = 0; j < pnum; j++) {
                weights[j] = sc.nextInt();
            }
            //arrange
            System.out.println(arrange(weights));
        }
    }

    public static int arrange(int[] weights){
        int total = 0; //总共耗时
        Arrays.sort(weights);
        //用最小的两个当工具人
        int last = weights.length;
        while (last>3){ //剩余超过三个人，每轮目的是把最重的两人运走
            //选择一人策略：最轻的人分两次把最重的两人带走
            int one = weights[0]*2 + weights[last-1] + weights[last-2];
            //选择两人策略：最轻的和次轻的过去，最轻的回来，两个最重的一起过去，次轻的把船开回
            int two = weights[0] + weights[1]*2 + weights[last-1];
            if(one>two){
                total += two;
            }else{
                total += one;
            }
            last -= 2;
        }
        //剩余三人，只能让最轻的人做工具人
        if(last==3){
            total += weights[0] + weights[last-1] + weights[last-2];
        }else{
            total += weights[1];//剩余二人，一起过去
        }
        return total;
    }
}
